package org.basis.algorithm.tree;

import org.basis.algorithm.tree.common.TreeNode;

import java.util.Stack;

/**
 * 树遍历
 * 先序遍历：对于任何一棵子树而言都是头节点先打印，然后是左右
 * 中序遍历：对于任何一棵子树而言都是左节点先打印，然后是中右
 * 后续遍历：对于任何一棵子树而言都是左节点先打印，然后是右中
 * 递归写法主要是要掌握递归序，对于树上的每个节点，如果用递归，那么一定会访问该节点三次，在不同的访问时机做打印就实现了前中后序遍历
 *
 * @author Mr_wenpan@163.com 2021/12/12 18:40
 */
public class ThreeTraverse {

    public static void main(String[] args) {

    }

    // ======================================递归方式遍历二叉树 ======================================

    public static void preorderByRecursion(TreeNode<Integer> head) {
        // base case
        if (head == null) {
            return;
        }
        // 先序遍历，在递归序中第一次访问某个节点时就打印
        System.out.print(head.data + "   ");
        preorderByRecursion(head.left);
        preorderByRecursion(head.right);
    }

    public static void inorderByRecursion(TreeNode<Integer> head) {
        // base case
        if (head == null) {
            return;
        }
        // 中序遍历，在递归序中第二次访问某个节点是进行打印
        inorderByRecursion(head.left);
        System.out.print(head.data + "   ");
        inorderByRecursion(head.right);
    }

    public static void postorderByRecursion(TreeNode<Integer> head) {
        // base case
        if (head == null) {
            return;
        }
        postorderByRecursion(head.left);
        postorderByRecursion(head.right);
        // 后续遍历，在递归序中第三次访问某个节点时再打印
        System.out.print(head.data + "   ");
    }

    // ======================================非递归方式遍历二叉树 ======================================

    public static void preOrderByStack(TreeNode<Integer> head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode<Integer>> stack = new Stack<>();
        // 先将头压栈
        stack.push(head);
        while (!stack.isEmpty()) {
            TreeNode<Integer> pop = stack.pop();
            System.out.println(pop.data + "   ");
            // 孩子节点压栈，先压右再压左
            stack.push(head.right);
            stack.push(head.left);
        }
    }

    /**
     * 非递归的中续遍历方式（核心思想：任何一棵树都能被左边界分解）
     */
    public static void inOrderByStack(TreeNode<Integer> head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode<Integer>> stack = new Stack<>();
        while (!stack.isEmpty() || head != null) {
            // 先将所有左边界压栈
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                // 弹出就打印，对弹出元素的右孩子的所有左孩子进行继续压栈
                TreeNode<Integer> pop = stack.pop();
                System.out.print(pop.data + "   ");
                head = pop.right;
            }
        }
    }

    /**
     * 非递归的后续遍历方式（核心：[左右中] 和先序遍历 [中左右] 非常像，
     * 先序遍历使用了一个栈，从头节点开始对于每个节点都是先压头，再压右再压左，弹出就打印。
     * 那么如果是先压右再压左，那么弹出顺序不就得到顺序 [左右中] 了吗）
     */
    public static void postOrderByStack(TreeNode<Integer> head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode<Integer>> stack1 = new Stack<>();
        Stack<TreeNode<Integer>> stack2 = new Stack<>();

        // 这里类似于先序遍历
        stack1.push(head);
        while (!stack1.isEmpty()) {
            // 这里弹出先不打印，暂时压入到stack2中
            TreeNode<Integer> pop = stack1.pop();
            stack2.push(pop);
            // 先压左再压右
            if (pop.left != null) {
                stack1.push(pop.left);
            }
            if (pop.right != null) {
                stack1.push(pop.right);
            }
        }

        // 最后将stack2的元素倒出来就是后续遍历
        while (!stack2.isEmpty()) {
            TreeNode<Integer> pop = stack2.pop();
            System.out.print(pop.data + "   ");
        }
    }

}
